package day7;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class ch3 {


    public boolean canFinish(int numCourses, int[][] prerequisites) {

        HashMap<Integer,Integer> node = new HashMap<>();
        HashMap<Integer, ArrayList<Integer>> edge = new HashMap<>();

        for (int i = 0; i < numCourses; i++) {
            node.put(i,0);
        }
        for (int i = 0; i < prerequisites.length; i++) {
            int x = prerequisites[i][0];
            int y = prerequisites[i][1];
            if(!edge.containsKey(x)) edge.put(x,new ArrayList<>());
            edge.get(x).add(y);
            node.put(y, node.get(y)+1);
        }
        int sum = 0;
        ArrayList<Integer> all = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            if(node.get(i)==0){
                all.add(i);
                sum++;
            }
        }
        while (!all.isEmpty()){
            int num = all.size();
            for (int i = 0; i < num; i++) {
                ArrayList<Integer> list = edge.getOrDefault(all.remove(0),null);
                if(list==null) continue;
                for(Integer n:list){
                    node.put(n, node.get(n)-1);
                    if(node.get(n)==0){
                        sum++;
                        all.add(n);
                    }
                }
            }
        }

        if(sum==numCourses) return true;

        return false;
    }




}
